package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/22 10:48
 */
public class C44 {

    // '?' 可以匹配任何单个字符。
    // '*' 可以匹配任意字符串（包括空字符串）。
    // 从前往后匹配.
    public static boolean isMatch(String s, String p) {
        int[][] dp = new int[s.length()+1][p.length()+1];
        return process(s.toCharArray(), p.toCharArray(), 0, 0, dp);
    }

    public static boolean process(char[] s1, char[] s2, int i, int j, int[][] dp) {
        if(dp[i][j] != 0) return dp[i][j] == 1;
        boolean ans = false;
        if (i == s1.length) {
            // 如果我结束了, 你还没结束, 你后边必须全都是*
            ans = true;
            for (; j < s2.length; j++) {
                if (s2[j] != '*') {
                    ans = false;
                    break;
                }
            }
        }else
        if (j == s2.length) ans = false;
        else if (s2[j] == '?') {     // 可以匹配一个, 且必须匹配一个
            ans = process(s1, s2, i + 1, j + 1, dp);
        } else if (s2[j] == '*') {
            // 1. 0 - ? 个字符,
            for (int k = 0; k <= s1.length - i; k++) {
                if (process(s1, s2, i + k, j + 1, dp)) {
                    ans = true;
                    break;
                }
            }
        } else {     // 普通字符必须严格相等
            ans = s1[i] == s2[j] && process(s1, s2, i + 1, j + 1, dp);
        }
        dp[i][j] = ans ? 1: -1;
        return ans;
    }


    // for test
    public static void main(String[] args) {
        String s = "aaaaaa";
        String p = "*a";
        System.out.println(isMatch(s, p));
    }

}
